import java.util.*;

import static javax.swing.Spring.height;

/**
 * @author: 子龙
 */

public class BinaryTree {

    static  class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;


        public TreeNode(char val){
            this.val=val;
        }
    }

    public TreeNode createTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.left=F;
        C.right=G;
        E.right=H;

        return A;
    }

    /**
     * 前序
     * @param root
     */
    void preOrder(TreeNode root){
        if(root==null) return;
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

    /**
     * 中序
     * @param root
     */
    void inOrder(TreeNode root){
        if(root==null) return;
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }


    /**
     * 后序
     * @param root
     */
    void postOrder(TreeNode root){
        if(root==null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }


    public List<Character> preOrderTraversal(TreeNode root){
        List<Character> list=new ArrayList<>();
        if(root==null) return list;
        list.add(root.val);
        List<Character> left=preOrderTraversal(root.left);
        list.addAll(left);
        List<Character> right=preOrderTraversal(root.right);
        list.addAll(right);
        return list;
    }

    int size (TreeNode root){
        if(root==null) return 0;
        return size(root.left)+size(root.right)+1;
    }

    int count=0;
    int size2 (TreeNode root){
        if(root==null) return 0;
        count++;
        size2(root.left);
        size2(root.right);
        return count;
    }

    int count2=0;
    public int getLeafNodeCount(TreeNode root){
        if(root==null) {
            return 0;
        }
        if(root.left==null && root.right==null){
            count2++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
        return count2;
    }

    public int getLeafNodeCount2(TreeNode root) {
        // 基准条件：如果节点为null，返回0
        if (root == null) {
            return 0;
        }

        // 如果是叶子节点（左右子树都为null），返回1
        if (root.left == null && root.right == null) {
            return 1;
        }

        // 否则递归计算左子树和右子树的叶子节点数并相加
        return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
    }


    public int getKLevelNodeCount(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
        if(k==1){
            return 1;
        }
        return getKLevelNodeCount(root.left, k-1) + getKLevelNodeCount(root.right, k-1);
    }

    public int getHeight(TreeNode root){
        if(root==null) return 0;

        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);
        return Math.max(leftHeight,rightHeight)+1;
    }

    public Boolean findVal(TreeNode root, char val){
        if(root==null) {
            return false;
        }
        if(root.val==val) {
            System.out.println(val);
            return true;
        }
        findVal(root.left,val);
        findVal(root.right,val);
       return false;
    }


    public boolean isSameTree(TreeNode p, TreeNode q) {

        if(p!=null && q==null || p==null && q!=null){
            return false;
        }

        if (p == null && q == null) {
            return true;
        }
        //同时遍历两颗 二叉树
        if(isSameTree(p.left, q.left) && isSameTree(p.right, q.right)) {
            if(p.val==q.val) {
                return true;
            }
            return false;
        }
        return false;

    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        // 子树为null，认为是任何树的子树
        if (subRoot == null) {
            return true;
        }
        // 主树为null但子树不为null，不可能是子树
        if (root == null) {
            return false;
        }

        // 情况1：当前节点开始的子树与subRoot相同
        if (isSameTree(root, subRoot)) {
            return true;
        }

        // 情况2：subRoot是左子树的子树，或者是右子树的子树
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);

    }

    public TreeNode invertTree(TreeNode root) {
        if(root==null){
            return null;
        }
        TreeNode temp=root.right;
        root.right=root.left;
        root.left=temp;

        invertTree(root.left);
        invertTree(root.right);

        return root;

    }


    public boolean isSymmetric(TreeNode root) {

        if(root==null){
            return true;
        }
        if(root.left!=null && root.right==null || root.left==null && root.right!=null){
            return false;
        }
        if(root.left==null && root.right==null){
            return true;
        }

        return isMirror(root.left,root.right);
    }

    private boolean isMirror(TreeNode t1, TreeNode t2) {
        // 两个节点都为null，对称
        if (t1 == null && t2 == null) return true;
        // 一个为null，一个不为null，不对称
        if (t1 == null || t2 == null) return false;
        // 当前节点值相等，且t1的左子树与t2的右子树对称，t1的右子树与t2的左子树对称
        return (t1.val == t2.val)
                && isMirror(t1.left, t2.right)
                && isMirror(t1.right, t2.left);
    }



    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        if(Math.abs(height(root.left)-height(root.right))<=1
                && isBalanced(root.left)
                && isBalanced(root.right)){
            return true;
        }
        return false;
    }

    private int height(TreeNode root) {
        if(root==null){
            return 0;
        }
        int leftHeight=height(root.left);
        int rightHeight=height(root.right);
        return Math.max(leftHeight,rightHeight)+1;
    }


    /**
     * 层序遍历
     * @param root
     */
    public  void levelOrder(TreeNode root) {
        if(root==null){
            return;
        }

        Queue<TreeNode> queue=new LinkedList<>();

        queue.offer(root);

        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            System.out.print(cur.val+" ");
            if(cur.left!=null) queue.offer(cur.left);
            if(cur.right!=null) queue.offer(cur.right);
        }

    }


    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> res=new ArrayList<>();

        if(root==null){
            return res;
        }

        Queue<TreeNode> queue=new LinkedList<>();

        queue.offer(root);

        while(!queue.isEmpty()){
            int size=queue.size();
            List<Integer> list=new ArrayList<>();
            while(size!=0){
                TreeNode cur=queue.poll();
                //list.add(cur.val);
//                System.out.print(cur.val+" ");
                if(cur.left!=null) queue.offer(cur.left);
                if(cur.right!=null) queue.offer(cur.right);
                size--;
            }
            res.add(list);

        }

        return res;
    }

    /**
     * 完全二叉树
     * @param root
     */
    public  boolean levelOrder3(TreeNode root) {
        if(root==null){
            return true;
        }

        Queue<TreeNode> queue=new LinkedList<>();

        queue.offer(root);

        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            if(cur!=null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }


        }

        while(!queue.isEmpty()){
            TreeNode peek=queue.peek();
            if(peek!=null){
                return false;
            }
            queue.poll();
        }
        return true;


    }


    /**
     *
     * @param root
     * @param node 找的节点
     * @param stack 存储到栈
     */
        private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){
        if(root==null){
            return false;
        }
        stack.push(root);

        if(root==node){
            return true;
        }

        boolean ret= getPath(root.left,node,stack);
        if (ret){
            return true;
        }
        ret= getPath(root.right,node,stack);
        if (ret){
            return true;
        }
         stack.pop();
        return false;



        }

    /**
     * 找公共祖先
     * @param root
     * @param p
     * @param q
     * @return
     */
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root==null){
                return null;
            }
            Stack<TreeNode> stackP=new Stack<>();
            Stack<TreeNode> stackQ=new Stack<>();

            getPath(root,p,stackP);
            getPath(root,q,stackQ);

            int sizeP=stackP.size();
            int sizeQ=stackQ.size();

            if(sizeP>sizeQ){
                int size=sizeP-sizeQ;
                while(size!=0){
                    stackP.pop();
                    size--;
                }
            }else {
                int size=sizeQ-sizeP;
                while(size!=0){
                    stackQ.pop();
                    size--;
                }
            }

            while(!stackP.isEmpty() && !stackQ.isEmpty()){
                if(stackP.peek()==stackQ.peek()){
                    return stackP.pop();
                }else {
                    stackQ.pop();
                    stackP.pop();
                }
            }
            return null;
        }


    /**
     * 根据二叉树创建字符串
     * @param root
     * @return
     */
    public String tree2str(TreeNode root) {
        StringBuilder stringBuilder=new StringBuilder();
        tree2strChild(root,stringBuilder);
        return stringBuilder.toString();
    }

    public void tree2strChild(TreeNode t,StringBuilder stringBuilder){
        if(t==null){
            return ;
        }
        stringBuilder.append(t.val);
        if(t.left!=null){
            stringBuilder.append("(");
            tree2strChild(t.left,stringBuilder);
            stringBuilder.append(")");
        }else{
            if(t.right==null){
                return;
            }else{
                stringBuilder.append("()");
            }
        }

        if(t.right!=null){
            stringBuilder.append("(");
            tree2strChild(t.right,stringBuilder);
            stringBuilder.append(")");
        }else{
            return;
        }
    }

    /**
     * 非递归前序遍历
     * @param root
     * @return
     */
    public void preorderTraversal(TreeNode root) {
        if(root==null){
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        stack.push(root);
        TreeNode cur=root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                System.out.println(cur.val+" ");
                cur = cur.left;
            }
            TreeNode top=stack.pop();
            cur=top.right;
        }
    }

    /**
     * 非递归中序遍历
     * @param root
     * @return
     */
    public void inorderTraversal(TreeNode root) {
        if(root==null){
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        stack.push(root);
        TreeNode cur=root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);

                cur = cur.left;
            }
            TreeNode top=stack.pop();
            System.out.println(cur.val+" ");
            cur=top.right;
        }
    }

    /**
     * 非递归后序遍历
     * @param root
     * @return
     */
    public void postorderTraversal(TreeNode root) {
        if(root==null){
            return;
        }
        Stack<TreeNode> stack=new Stack<>();

        TreeNode cur=root;
        TreeNode prev=null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);

                cur = cur.left;
            }
            TreeNode top=stack.peek();
            if (top.right == null || top.right == prev) {
                System.out.println(cur.val+" ");
                stack.pop();
                prev=top;
            }else {
                cur = top.right;
            }
        }
    }


    /**
     * 中序+后续构建二叉树
     */
    public int postIndex;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex=postorder.length-1;
        return buildTreeChild(inorder,postorder,0,inorder.length-1);
    }

    public TreeNode buildTreeChild(int[] inorder, int[] postorder,int inbegin,int inend){
        if(inbegin>inend){
            return null;
        }

        TreeNode root=new TreeNode((char) postorder[postIndex]);
        int rootIndex=findVal(inorder,inbegin,inend,postorder[postIndex]);

        postIndex--;
        root.right=buildTreeChild(inorder,postorder,rootIndex+1,inend);
        root.left=buildTreeChild(inorder,postorder,inbegin,rootIndex-1);

        return root;


    }

    private int findVal(int[] inorder,int inbegin,int inend,int val){
        for(int i=inbegin;i<=inend;i++){
            if(inorder[i]==val){
                return i;
            }
        }
        return -1;
    }

}